1. Field of the Invention
The present invention is directed to a method, apparatus, and computer readable storage for producing a subdivision surface that accurately approximates a Boolean combination of two input subdivision surfaces.
2. Description of the Related Art
Subdivision surfaces are a known modeling tool in computer graphics. They are ideal for modeling because they can be smoothly curved (like spline surfaces) and they can have any topology (like polygon meshes).
A subdivision surface starts with a polygonal base mesh. This base mesh is then repeatedly sub-divided and modified according to selected subdivision rules until a desired, smooth surface is created. For example, a square base mesh typically (although it varies depending on the subdivision scheme chosen) results in a circle. Thus, subdivision surfaces allow an artist or an engineer to work with polygons (either 2D or 3D) which are easy to work with (typically easier than curved surfaces) and then once a model is created the model can be smoothed into a smooth curved surface using subdivision surfaces. Catmull-Clark subdivision surfaces are a popular scheme of subdivision surfaces. See E. Catmull, J. Clark, “Recursively Generated B-Spline Surfaces on Arbitrary Topological Meshes,” in Computer Aided Design Oct. 6 1978, for the original paper describing the Catmull-Clark subdivision rules, and which is incorporated by reference herein. Further, many other papers have been written describing subdivision rules and particularly Catmull-Clark subdivision rules.
Boolean operations (union, difference, intersection) are commonly used tools for modeling. For example, a Boolean operation such as intersection would take two intersecting objects, and produce a new object which is the mathematical intersection of the two objects.
The prior art affords no easy way to perform Boolean operations on Catmull-Clark subdivision surfaces.
Therefore, what is needed is an accurate and easy way that Boolean operations on subdivision surfaces can be performed.